1407B - Big Vova - CodeForces Solution

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define lld long double
#define for0(i,n) for(int i=0; i<n; i++)
#define for1(i,n) for(int i=1; i<=n; i++)
#define loop(i,a,b) for(int i=a; i<b; i++)
#define bloop(i,a,b) for(int i=a; i>=b; i--)
#define tc(t) int t; cin>>t; while(t--)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
#define pi pair<int,int>
#define vpi vector<pi>
#define all(a) a.begin(),a.end()
#define rall(a) a.end(),a.begin()

#define py cout<<"YES\n";
#define pn cout<<"NO\n";
#define PI 3.141592653589793238
#define mod (int) 1000000007
#define infinity (int) (1e18)


bool isPerfectSquare(long double x)
{
    // Find floating point value of
    // square root of x.
    if (x >= 0) {
  long long sr = sqrt(x);
        // if product of square root
        //is equal, then
        // return T/F
        return (sr * sr == x);
    }
    // else return false if n<0
       return false;
}


bool prime (long long int n) {
  bool prime = 1;
  if (n == 1) {
      return 0;
  }
  else {
      for (long long int i = 2; i <= n/2 ; i++) {
          if (n % i == 0) {
              prime = 0;
              break ;
          } 
      }
        return prime;
  }
}


// precompute number is prime or not using seive 
// const int k=1e7;
// vector<bool> v(k,1);

// // paste it inside main fun|
// v[0]=v[1]=false;           <-from here
//  for(int i=2;i<k;i++){
//     if(v[i]==true)
//     for(int j=2*i; j<k; j=j+i){
//         if(v[j]==true)
//         v[j]=false;
//     }
//  }

int main(){
 tc(t){    
int n;
cin>>n;
const int l=1e4;
vi arr(n),checker(n,0),ans;
for0(i,n){
 cin>>arr[i];
}
int M= *max_element(all(arr));
int maxI= max_element(all(arr))-arr.begin();
checker[maxI]=1;
ans.push_back(M);
int g=M,ind=maxI;

while(ans.size()!=n){
    int Ma = 1;
    for0(i,n){
        if(checker[i]==0){
        int N=gcd(g,arr[i]);
        if(N>=Ma){
            Ma=N;
            ind =i;
        }
        // if(gcd(arr[i],g)<g){
        //     g=gcd(arr[i],g);
        //     ind=i;
        // }
        }
    }
    g=Ma;
    ans.push_back(arr[ind]);
    checker[ind]=1;
}

for(auto k:ans){
    cout<<k<<" ";
}
cout<<endl;

 }
return 0;
}